// """
// A nonogram is a logic puzzle, similar to a crossword, in which the player is given a blank grid and has to color it according to some instructions. Specifically, each cell can be either black or white, which we will represent as 0 for black and 1 for white.

// +------------+
// | 1  1  1  1 |
// | 0  1  1  1 |
// | 0  1  0  0 |
// | 1  1  0  1 |
// | 0  0  1  1 |
// +------------+

// For each row and column, the instructions give the lengths of contiguous runs of black (0) cells. For example, the instructions for one row of [ 2, 1 ] indicate that there must be a run of two black cells, followed later by another run of one black cell, and the rest of the row filled with white cells.

// These are valid solutions: [ 1, 0, 0, 1, 0 ] and [ 0, 0, 1, 1, 0 ] and also [ 0, 0, 1, 0, 1 ]
// This is not valid: [ 1, 0, 1, 0, 0 ] since the runs are not in the correct order.
// This is not valid: [ 1, 0, 0, 0, 1 ] since the two runs of 0s are not separated by 1s.

// Your job is to write a function to validate a possible solution against a set of instructions. Given a 2D matrix representing a player's solution; and instructions for each row along with additional instructions for each column; return True or False according to whether both sets of instructions match.

// Example instructions #1

// matrix1 = [[1,1,1,1],
//            [0,1,1,1],
//            [0,1,0,0],
//            [1,1,0,1],
//            [0,0,1,1]]
// rows1_1    =  [], [1], [1,2], [1], [2]
// columns1_1 =  [2,1], [1], [2], [1]
// validateNonogram(matrix1, rows1_1, columns1_1) => True

// Example solution matrix:
// matrix1 ->
//                                    row
//                 +------------+     instructions
//                 | 1  1  1  1 | <-- []
//                 | 0  1  1  1 | <-- [1]
//                 | 0  1  0  0 | <-- [1,2]
//                 | 1  1  0  1 | <-- [1]
//                 | 0  0  1  1 | <-- [2]
//                 +------------+
//                   ^  ^  ^  ^
//                   |  |  |  |
//   column       [2,1] | [2] |
//   instructions      [1]   [1]

// Example instructions #2

// (same matrix as above)
// rows1_2    =  [], [], [1], [1], [1,1]
// columns1_2 =  [2], [1], [2], [1]
// validateNonogram(matrix1, rows1_2, columns1_2) => False

// The second and third rows and the first column do not match their respective instructions.

// Example instructions #3

// matrix2 = [
// [ 1, 1 ],
// [ 0, 0 ],
// [ 0, 0 ],
// [ 1, 0 ]
// ]
// rows2_1    = [], [2], [2], [1]
// columns2_1 = [1, 1], [3]
// validateNonogram(matrix2, rows2_1, columns2_1) => False

// The black cells in the first column are not separated by white cells.

// n: number of rows in the matrix
// m: number of columns in the matrix
// """

// matrix1 = [
//     [1,1,1,1], # []
//     [0,1,1,1], # [1] -> a single run of _1_ zero (i.e.: "0")
//     [0,1,0,0], # [1, 2] -> first a run of _1_ zero, then a run of _2_ zeroes
//     [1,1,0,1], # [1]
//     [0,0,1,1], # [2]
// ]

// # True
// rows1_1 = [[],[1],[1,2],[1],[2]]
// columns1_1 = [[2,1],[1],[2],[1]]
// # False
// rows1_2 = [[],[],[1],[1],[1,1]]
// columns1_2 = [[2],[1],[2],[1]]

// matrix2 = [
//     [1,1],
//     [0,0],
//     [0,0],
//     [1,0]
// ]
// # False
// rows2_1 = [[],[2],[2],[1]]
// columns2_1 = [[1,1],[3]]

// matrix1 = [[1,1,1,1],
//            [0,1,1,1],
//            [0,1,0,0],
//            [1,1,0,1],
//            [0,0,1,1]]
// rows1_1    =  [], [1], [1,2], [1], [2]
// columns1_1 =  [2,1], [1], [2], [1]

package main

import "fmt"

///////////////////
// 一句话
// 横竖分开看
// 数0的时候记得解决计数器为0的时候

func isValidNonogram(matrix [][]int, row, col [][]int) bool {
	// validation
	if len(matrix) != len(row) || len(matrix[0]) != len(col) {
		return false
	}
	return isValidRow(matrix, row) && isValidCol(matrix, col)
}

func isValidRow(matrix [][]int, row [][]int) bool {
	for i := 0; i < len(matrix); i++ {
		// scan each line
		solution := []int{}
		j := 0
		cnt := 0
		for j < len(matrix[i]) {
			if matrix[i][j] == 0 {
				cnt++
			} else {
				if cnt != 0 {
					solution = append(solution, cnt)
					cnt = 0
				}

			}

			j++
		}
		if cnt != 0 {
			solution = append(solution, cnt)
		}
		if compare(solution, row[i]) == false {
			return false
		}
	}
	return true
}

func isValidCol(matrix [][]int, col [][]int) bool {
	for i := 0; i < len(matrix[0]); i++ {
		// scan each line
		solution := []int{}
		j := 0
		cnt := 0
		for j < len(matrix) {
			if matrix[j][i] == 0 {
				cnt++
			} else {
				if cnt != 0 {
					solution = append(solution, cnt)
					cnt = 0
				}

			}

			j++
		}
		if cnt != 0 {
			solution = append(solution, cnt)
		}
		if compare(solution, col[i]) == false {
			return false
		}
	}
	return true
}

func compare(s1, s2 []int) bool {
	if len(s1) != len(s2) {
		return false
	}
	for i := 0; i < len(s1); i++ {
		if s1[i] != s2[i] {
			return false
		}
	}
	return true
}

func main() {
	input := [][]int{
		[]int{1, 1, 1, 1},
		[]int{0, 1, 1, 1},
		[]int{0, 1, 0, 0},
		[]int{1, 1, 0, 1},
		[]int{0, 0, 1, 1},
	}
	//[],[1],[1,2],[1],[2]
	row := [][]int{
		[]int{},
		[]int{1},
		[]int{1, 2},
		[]int{1},
		[]int{2},
	}
	//[[2,1],[1],[2],[1]]
	col := [][]int{
		[]int{2, 1},
		[]int{1},
		[]int{2},
		[]int{1},
	}
	// fmt.Println(isValidRow(input, row))
	// fmt.Println(isValidCol(input, col))
	// matrix2 = [
	//     [1,1],
	//     [0,0],
	//     [0,0],
	//     [1,0]
	// ]
	// # False
	// rows2_1 = [[],[2],[2],[1]]
	// columns2_1 = [[1,1],[3]]

	input2 := [][]int{
		[]int{1, 1},
		[]int{0, 0},
		[]int{0, 0},
		[]int{1, 0},
	}
	//[],[1],[1,2],[1],[2]
	row2 := [][]int{
		[]int{},
		[]int{2},
		[]int{2},
		[]int{1},
	}
	//[[2,1],[1],[2],[1]]
	col2 := [][]int{
		[]int{1, 1},
		[]int{3},
	}
	fmt.Println(isValidNonogram(input, row, col))
	fmt.Println(isValidNonogram(input2, row2, col2))
}
